<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>When to use?</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 16. Boost.Intrusive">
<link rel="prev" href="usage.html" title="How to use Boost.Intrusive">
<link rel="next" href="concepts_summary.html" title="Concept summary">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="usage.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="concepts_summary.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="intrusive.usage_when"></a><a class="link" href="usage_when.html" title="When to use?">When to use?</a>
</h2></div></div></div>
<p>
      Intrusive containers can be used for highly optimized algorithms, where speed
      is a crucial issue and:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          additional memory management should be avoided.
        </li>
<li class="listitem">
          the programmer needs to efficiently track the construction and destruction
          of objects.
        </li>
<li class="listitem">
          exception safety, especially the no-throw guarantee, is needed.
        </li>
<li class="listitem">
          the computation of an iterator to an element from a pointer or reference
          to that element should be a constant time operation.
        </li>
<li class="listitem">
          it's important to achieve a well-known worst-time system response.
        </li>
<li class="listitem">
          localization of data (e.g. for cache hit optimization) leads to measurable
          effects.
        </li>
</ul></div>
<p>
      The last point is important if you have a lot of containers over a set of elements.
      E.g. if you have a vector of objects (say, <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">Object</span><span class="special">&gt;</span></code>), and you also have a list storing a subset
      of those objects (<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special">&lt;</span><span class="identifier">Object</span><span class="special">*&gt;</span></code>),
      then operating on an Object from the list iterator (<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special">&lt;</span><span class="identifier">Object</span><span class="special">*&gt;::</span><span class="identifier">iterator</span></code>) requires two steps:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          Access from the iterator (usually on the stack) to the list node storing
          a pointer to <code class="computeroutput"><span class="identifier">Object</span></code>.
        </li>
<li class="listitem">
          Access from the pointer to <code class="computeroutput"><span class="identifier">Object</span></code>
          to the Object stored in the vector.
        </li>
</ul></div>
<p>
      While the objects themselves are tightly packed in the memory of the vector
      (a vector's memory is guaranteed to be contiguous), and form something like
      a data block, list nodes may be dispersed in the heap memory. Hence depending
      on your system you might get a lot of cache misses. The same doesn't hold for
      an intrusive list. Indeed, dereferencing an iterator from an intrusive list
      is performed in the same two steps as described above. But the list node is
      already embedded in the Object, so the memory is directly tracked from the
      iterator to the Object.
    </p>
<p>
      It's also possible to use intrusive containers when the objects to be stored
      can have different or unknown size. This allows storing base and derived objects
      in the same container, as shown in the following example:
    </p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>

<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span>

<span class="comment">//An abstract class that can be inserted in an intrusive list</span>
<span class="keyword">class</span> <span class="identifier">Window</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">list_base_hook</span><span class="special">&lt;&gt;</span>
<span class="special">{</span>
   <span class="keyword">public</span><span class="special">:</span>
   <span class="comment">//This is a container those value is an abstract class: you can't do this with std::list.</span>
   <span class="keyword">typedef</span> <span class="identifier">list</span><span class="special">&lt;</span><span class="identifier">Window</span><span class="special">&gt;</span> <span class="identifier">win_list</span><span class="special">;</span>

   <span class="comment">//A static intrusive list declaration</span>
   <span class="keyword">static</span> <span class="identifier">win_list</span> <span class="identifier">all_windows</span><span class="special">;</span>

   <span class="comment">//Constructor. Includes this window in the list</span>
   <span class="identifier">Window</span><span class="special">()</span>             <span class="special">{</span>  <span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(*</span><span class="keyword">this</span><span class="special">);</span>  <span class="special">}</span>
   <span class="comment">//Destructor. Removes this node from the list</span>
   <span class="keyword">virtual</span> <span class="special">~</span><span class="identifier">Window</span><span class="special">()</span>    <span class="special">{</span>  <span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">win_list</span><span class="special">::</span><span class="identifier">s_iterator_to</span><span class="special">(*</span><span class="keyword">this</span><span class="special">));</span>  <span class="special">}</span>
   <span class="comment">//Pure virtual function to be implemented by derived classes</span>
   <span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">()</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span>
<span class="special">};</span>

<span class="comment">//The static intrusive list declaration</span>
<span class="identifier">Window</span><span class="special">::</span><span class="identifier">win_list</span> <span class="identifier">Window</span><span class="special">::</span><span class="identifier">all_windows</span><span class="special">;</span>

<span class="comment">//Some Window derived classes</span>
<span class="keyword">class</span> <span class="identifier">FrameWindow</span> <span class="special">:</span>  <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span>  <span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">()</span> <span class="identifier">BOOST_OVERRIDE</span> <span class="special">{/**/}</span> <span class="special">};</span>

<span class="keyword">class</span> <span class="identifier">EditWindow</span> <span class="special">:</span>  <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span>  <span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">()</span> <span class="identifier">BOOST_OVERRIDE</span> <span class="special">{/**/}</span> <span class="special">};</span>

<span class="keyword">class</span> <span class="identifier">CanvasWindow</span> <span class="special">:</span>  <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span>  <span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">()</span> <span class="identifier">BOOST_OVERRIDE</span> <span class="special">{/**/}</span> <span class="special">};</span>

<span class="comment">//A function that prints all windows stored in the intrusive list</span>
<span class="keyword">void</span> <span class="identifier">paint_all_windows</span><span class="special">()</span>
<span class="special">{</span>
   <span class="keyword">for</span><span class="special">(</span><span class="identifier">Window</span><span class="special">::</span><span class="identifier">win_list</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">i</span><span class="special">(</span><span class="identifier">Window</span><span class="special">::</span><span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">begin</span><span class="special">())</span>
                                <span class="special">,</span> <span class="identifier">e</span><span class="special">(</span><span class="identifier">Window</span><span class="special">::</span><span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">end</span><span class="special">())</span>
      <span class="special">;</span> <span class="identifier">i</span> <span class="special">!=</span> <span class="identifier">e</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span>
      <span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">Paint</span><span class="special">();</span>
<span class="special">}</span>

<span class="comment">//...</span>

<span class="comment">//A class derived from Window</span>
<span class="keyword">class</span> <span class="identifier">MainWindow</span>  <span class="special">:</span>  <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span>
   <span class="identifier">FrameWindow</span>   <span class="identifier">frame_</span><span class="special">;</span>  <span class="comment">//these are derived from Window too</span>
   <span class="identifier">EditWindow</span>    <span class="identifier">edit_</span><span class="special">;</span>
   <span class="identifier">CanvasWindow</span>  <span class="identifier">canvas_</span><span class="special">;</span>

   <span class="keyword">public</span><span class="special">:</span>
   <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">()</span> <span class="identifier">BOOST_OVERRIDE</span> <span class="special">{/**/}</span>
   <span class="comment">//...</span>
<span class="special">};</span>

<span class="comment">//Main function</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
   <span class="comment">//When a Window class is created, is automatically registered in the global list</span>
   <span class="identifier">MainWindow</span> <span class="identifier">window</span><span class="special">;</span>

   <span class="comment">//Paint all the windows, sub-windows and so on</span>
   <span class="identifier">paint_all_windows</span><span class="special">();</span>

   <span class="comment">//All the windows are automatically unregistered in their destructors.</span>
   <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
      Due to certain properties of intrusive containers they are often more difficult
      to use than their STL-counterparts. That's why you should avoid them in public
      interfaces of libraries. Classes to be stored in intrusive containers must
      change their implementation to store the hook and this is not always possible
      or desirable.
    </p>
</div>
<div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="usage.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="concepts_summary.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
